package com.basic;

import java.text.SimpleDateFormat;
import java.util.Date;
import java.util.Scanner;

public class NumTriangle {
	final static int n = 5;
	public static void main(String[] args) {
		long x = System.currentTimeMillis();
		int[][] a = new int[][]{{7,0,0,0,0},{3,8,0,0,0},{8,1,0,0,0},{2,7,4,4,0},{4,5,2,6,5}};
		int[][] maxSum = new int[n][n];
//		Scanner scanner = new Scanner(System.in);
		
		for(int i = 0;i < n;i++)
			for(int j = 0;j <= i;j++)
			{
//				a[i][j] = scanner.nextInt();
				maxSum[i][j] = -1;
			}
		System.out.println("\n" + Dfs(a,0,0,maxSum));
		long y = System.currentTimeMillis();
		Date date = new Date();
		SimpleDateFormat simpleDate = new SimpleDateFormat("yyyy-MM-dd hh:mm:ss");
		String da = simpleDate.format(date);
		System.out.println(da);
		System.out.println(y-x);
	}
	
	public static int Dfs(int[][] triangle,int i,int j,int[][] maxSum)
	{
		if(i == n-1)
		{
			return triangle[i][j];
		}
		if(maxSum[i][j] != -1)
			return maxSum[i][j];
		else {
			int x = Dfs(triangle,i+1,j,maxSum);
			int y = Dfs(triangle,i+1,j+1,maxSum);
			return maxSum[i][j] = x>y?x + triangle[i][j]:y + triangle[i][j];
		}
	}
}
